
\prob{0038}{$k$次对一次}

对于正奇数$k$和正整数$n$，求证：$1^k + 2^k + \dots + n^k$可以被$1 + 2 + \dots + n$整除。
\problabels{yellow/数论, green/证明题}

\subsection{依次证明}

基本思路：通过证明对于正奇数$k$和正整数$n, i$，有$n$整除$i^k + (n - i)^k$，从而应用到题中，进而分开证明$2(1^k + 2^k + \dots + n^k)$可以被$n$和$n + 1$整除。

首先我们需要证明：对于正奇数$k$和正整数$n, i$，有$n$整除$i^k + (n - i)^k$。

由于$k$为奇数，所以$(n - i)^k$展开后唯一没有$n$的一项是$(-i)^k = -i^k$，而该项由与$i^k$抵消。由于剩下的项全部含有$n$，因此$n$整除$i^k + (n - i)^k$。

又由$1 + 2 + \dots + n = \sfrac12n(n + 1)$可知，只要我们分别证明$2(1^k + 2^k + \dots + n^k)$可以被$n$和$n + 1$整除，即可证明命题。

首先我们可知：

\begin{align*}
  &\mathrel{\phantom=} 2(1^k + 2^k + \dots + n^k) \\
  &= (1^k + 2^k + \dots + (n - 1)^k + n^k) \\
  &+ (n^k + (n - 1)^k + \dots + 2^k + 1^k) \\
  &= (1^k + n^k) + (2^k + (n - 1)^k) + \dots + (n^k + 1^k) \\
  &= \sum_{i = 1}^n i^k + (n + 1 - i)^k \\
\end{align*}

根据开始的结论知，$i^k + (n + 1 - i)^k$可以被$n + 1$整除，因此$2(1^k + 2^k + \dots + n^k)$可以被$n + 1$整除。

又因为

\begin{align*}
  &\mathrel{\phantom=} 2(1^k + 2^k + \dots + n^k) \\
  &= 2(0^k + 1^k + 2^k + \dots + n^k) \\
  &= (0^k + 1^k + \dots + (n - 1)^k + n^k) \\
  &+ (n^k + (n - 1)^k + \dots + 1^k + 0^k) \\
  &= (0^k + n^k) + (1^k + (n - 1)^k) + \dots + (n^k + 0^k) \\
  &= \sum_{i = 0}^n i^k + (n - i)^k \\
\end{align*}

所以$2(1^k + 2^k + \dots + n^k)$亦可被$n$整除。

因此，$1^k + 2^k + \dots + n^k$可以被$1 + 2 + \dots + n$整除。证毕。
